(1) Field of the Invention
The present invention relates to an error-correcting and error-detecting system which carries out both a b-bit single burst block error-correcting operation and a double burst block error-detecting operation by utilizing a (k,l) type check matrix, i.e., the so-called H-matrix.
(2) Description of the Prior Art
Generally, in a large capacity memory system, error-correcting and error-detecting codes are widely used to improve the reliability of reading and writing operations therein. However, one bit error-correcting codes and two bit error-detecting codes have only been employed to improve the above-mentioned reliability, and accordingly, it is impossible to carry out an error-correcting operation when more errors occur in the memory system. Such a memory system usually stores a plurality of data bits as one block of information and a set of a plurality of such blocks of information composes one word. In the above memory system, when any error occurs therein, the error causes, as a whole, an error in one block of information. As a result, it is impossible to carry out such an error-correcting operation in a large capacity memory system.
In order to carry out the above-mentioned error-correcting operation, a high-speed error-correcting method was proposed in the article, entitled "b-Adjacent Error Correction" by D. C. Bossen in IBM J. Res. Develop., vol. 14, No. 4, pages 402 to 409, 1970, which discloses the correction of all single-bit errors as well as the correction of all single clusters of b-adjacent-bit errors. Furthermore, an expanded b-adjacent-bit correction has also been proposed by Se June Hong and Arvind M. Patel in the article entitled "A General Class of Maximal Codes for Computer Applications" in IEEE transactions on Computers, vol. C-21, No. 12, pages 1322 to 1331, December, 1972.
Based on the above two technical reports, various check-bits generating circuits were proposed. One of such check-bits generating circuits was proposed by us for solving the problem contained in the systems disclosed in the two technical reports. The problem disclosed in these reports is that the number of information bits is limited to (2.sup.b -1).times.b bits, i.e., (2.sup.b -1) blocks. Accordingly, it is disadvantageous that such number is limited to (2.sup.b -1).times.b, because the number of information bits is generally selected to be 2.sup.n (where n is a positive integer). For the purpose of eliminating the disadvantage, in our above-mentioned check-bits generating circuit, b bits of check-bits are further employed, and therefore the b-adjacent single burst error correcting operation and the b-adjacent double burst error detecting operation can be carried out with respect to information having the number of bits of up to 2.sup.b .times.b, i.e., 2.sup.b blocks. However, our above-mentioned check-bits generating circuit has the following defects. When it is intended to construct the check-bits generating circuit by utilizing a single LSI (Large Scale Integration) chip, this single LSI chip must be mounted with about six hundred gate circuits and provided with about eighty input/output pins. In reality, a conventional LSI chip can be provided with at most about four hundred gate circuits mounted thereon and provided with at most seventy input/output pins. Consequently, the check-bits generating circuit of the prior art must be divided into at least two circuit units so that each circuit unit can be constructed by utilizing a conventional LSI chip. There are two methods for dividing the check-bits generating circuit into two circuit units, each of which is constructed by utilizing the same conventional size LSI chip. However, in the first method, it is required to employ an additional operating circuit which functions to combine respective outputs from the two circuit units in order to produce check-bits. This feature is the defect of our above-mentioned check-bits generating circuit. In the second method, since the result obtained from one of the two circuit units is supplied to the other circuit unit, and an output is thereafter produced from the other of the two circuit units, it takes a relatively long time to produce check-bits. This feature is also a defect of our above-mentioned check-bits generating circuit.